# -*- coding: utf-8 -*-
"""
@Time ： 2023/4/16 10:43
@Auth ： 叶东宇
@File ：threeSum.py
"""

def threeSum(nums):
    dic = dict()
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] not in dic:
                dic[nums[i] + nums[j]] = [[i, j]]
            else:
                if [i, j] not in dic[nums[i] + nums[j]]:
                    dic[nums[i] + nums[j]].append([i, j])
    lis = []
    print(dic)
    for i in range(len(nums)):
        if 0 - nums[i] in dic:
            for j in dic[0 - nums[i]]:
                if i != j[0] and i != j[1]:
                    li = sorted([i, j[0], j[1]], key=lambda x: x)
                    if li not in lis:
                        lis.append(li)
    ta = []
    for k in lis:
        t_tmp = sorted([nums[k[0]], nums[k[1]], nums[k[2]]], key=lambda x: x)
        if t_tmp not in ta:
            ta.append(t_tmp)
    return ta

def from_leetcode(nums):
    nums = sorted(nums, key=lambda x:x)
    left = 0
    right = len(nums)-1
    change = left+1
    lis = []
    while right != 1:
        while left != (right-1):
            while change != right:
                if (nums[left] + nums[change] + nums[right]) == 0:
                    # tmp = sorted([nums[left], nums[change], nums[right]], key=lambda x:x)
                    tmp = [nums[left], nums[change], nums[right]]
                    if tmp not in lis:
                        lis.append(tmp)
                change += 1
            left += 1
            change = left + 1
        right -= 1
        left = 0
        change = left + 1
    return lis

def from_leetcode_1(nums):
    lis = []
    nums.sort()
    if len(nums) < 3:
        return []
    for i in range(len(nums)):
        if nums[i] > 0:
            return lis
        left = i + 1
        right = len(nums) - 1
        while left < right:
            if nums[i] + nums[left] + nums[right] < 0:
                left += 1
            elif nums[i] + nums[left] + nums[right] > 0:
                right -= 1
            else:
                if [nums[i], nums[left], nums[right]] not in lis:
                    lis.append([nums[i], nums[left], nums[right]])
                while nums[left] == nums[left+1]: left += 1
                while nums[right] == nums[right-1]: right -= 1
                left += 1
                right -= 1
    return lis

if __name__ == "__main__":
    nums = [-1,0,1,2,-1,-4]
    print(from_leetcode_1(nums))
